// 克隆图

package Leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

class solution_133 {

    // Definition for a Node.
    class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

    public HashSet<Node> hs = new HashSet<>();

    public Node cloneGraph(Node node) {
        Node result = new Node();
        dfs(node, result);
        return result;
    }

    public void dfs(Node node, Node result) {
        hs.add(node);
        List<Node> nb = node.neighbors;
        result.val = node.val;
        result.neighbors = new ArrayList<>(nb);
        for (int i = 0; i < nb.size(); i++) {
            if (!hs.contains(node.neighbors.get(i)))
                dfs(node.neighbors.get(i), result.neighbors.get(i));
        }
    }
}

// 深度优先遍历
public class Solution133 {

    // Definition for a Node.
    class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

    public Node cloneGraph(Node node) {
        HashMap<Node, Node> hm = new HashMap<>();

        if (node == null)
            return null;

        // 如果该结点已经被访问过了，则直接取克隆值返回
        if (hm.containsKey(node))
            return hm.get(node);

        // 如果该结点没有被访问过，则对其进行克隆并加入哈希表中
        Node clone = new Node(node.val, new ArrayList<>());
        hm.put(node, clone);

        // 对遍历该结点的邻居并更新其克隆结点的邻居列表
        for (Node nb : node.neighbors) {
            clone.neighbors.add(cloneGraph(nb));
        }
        return hm.get(node);
    }
}

// 广度优先遍历
class Solution133_2 {

    // Definition for a Node.
    class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

    public Node cloneGraph(Node node) {
        HashMap<Node, Node> hm = new HashMap<>();

        if (node == null)
            return null;
        // 克隆第一个结点并添加到哈希表
        hm.put(node, new Node(node.val, new ArrayList<>()));

        // 将第一个结点添加到队列里
        LinkedList<Node> queue = new LinkedList<>();
        queue.add(node);

        // 广度优先搜索
        while (!queue.isEmpty()) {
            // 获取队头元素
            Node removehead = queue.remove();
            // 访问队头元素的邻居
            for (Node nb : removehead.neighbors) {
                // 如果邻居没有被克隆则先克隆再加入队尾
                if (!hm.containsKey(nb)) {
                    Node clone = new Node(nb.val, new ArrayList<>());
                    hm.put(nb, clone);
                    queue.add(nb);
                }
                // 设置队头的克隆结点的邻居列表
                hm.get(removehead).neighbors.add(hm.get(nb));
            }
        }
        // 返回第一个结点的克隆
        return hm.get(node);
    }
}